package classical_problems_150;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class P_0024 {
    private static int precedence(String op){
        if(op.equals("/") || op.equals("*")){
            return 3;
        } else if(op.equals("+") || op.equals("-")){
            return 1;
        } else if(op.equals("~")){
            return 2;
        } else return 0;
    }

    private List<String> infix2RPN(String exp){
        List<String> rpn = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        int i=0;
        while(i < exp.length()){
            char c = exp.charAt(i);
            if(c!=' '){
                if(c=='('){
                    stack.push(String.valueOf(c));
                } else if(c==')'){
                    while(!stack.peek().equals("(")){
                        rpn.add(stack.pop());
                    }
                    stack.pop();
                } else if(c>='0' && c<='9'){
                    StringBuilder builder = new StringBuilder();
                    while(c>='0' && c<='9' && i<exp.length()){

                        builder.append(c);
                        i++;
                        if(i<exp.length())
                            c = exp.charAt(i);
                    }
                    rpn.add(builder.toString());
                    continue;
                } else {
                    if(c=='-' && (i==0 || exp.charAt(i-1)=='(')){
                        stack.push("~");
                    } else {
                        String op = String.valueOf(c);
                        int prior = precedence(op);
                        while(!stack.isEmpty() && precedence(stack.peek()) >= prior){
                            rpn.add(stack.pop());
                        }
                        stack.add(op);
                    }
                }
            }
            i++;
        }
        while(!stack.isEmpty()){
            rpn.add(stack.pop());
        }
        return rpn;
    }

    public int calculate(String s) {
        s = s.replace(" ", "");
        List<String> rpn = this.infix2RPN(s);
        Stack<Integer> stack = new Stack<>();
        for(String str: rpn){
            int val = 0;
            if(str.charAt(0) >= '0' && str.charAt(0) <= '9'){
                val = Integer.valueOf(str);
            } else if(str.charAt(0) == '~'){
                val = stack.pop();
                val = -val;
            } else{
                int b = stack.pop();
                int a = stack.pop();
                if(str.charAt(0) == '+'){
                    val = a+b;
                } else if(str.charAt(0) == '-'){
                    val = a-b;
                } else if(str.charAt(0) == '*'){
                    val = a*b;
                } else if(str.charAt(0) == '/'){
                    val = a/b;
                }
            }
            stack.push(val);
        }
        int res = stack.pop();
        return res;
    }

    public static void main(String[] args){
        P_0024 solution = new P_0024();
        solution.calculate("(1+(4+5+2)-3)+(6+8)");
        return ;
    }
}
